package com.zhang;

/**
 * @author ZhangJiXin
 * @Description UnionFind -- QU(快速合并) -- S(数量)优化
 * @date 2021/4/30 9:52
 */
public  class UnionFind_QU_S extends UnionFind_QU{
    private int[] size ;

    /**
     * 创建一个跟集合数组一样长度的数组 记录根节点所在的集合的元素数量
     * @Author ZhangJiXin
     * @Date 2021/4/30 11:27
     * @param capacity:
     * @return: null
     */
    public UnionFind_QU_S(int capacity) {
       super(capacity);

       size = new int[capacity];
        for (int i = 0; i < size.length; i++) {
            size[i] = 1;
        }
    }

    /**
     * 合并的时候 判断 元素数量少的集合 指向元素多的集合
     * 可以降低集合退化成链表的概率
     * @Author ZhangJiXin
     * @Date 2021/4/30 11:29
     * @param v1:
     * @param v2:
     * @return: void
     */
    @Override
    public void union(int v1, int v2){
        int v1Root = find(v1);
        int v2Root = find(v2);
        if (v1Root == v2Root){
            return;
        }

        if (size[v1Root] < size[v2Root]){
            parents[v1Root] = v2Root;
            size[v2Root] += size[v1Root];
        }else {
            parents[v2Root] = v1Root;
            size[v1Root] += size[v2Root];
        }
    }

}
